package test.n00200;


import java.util.ArrayList;
import java.util.List;

public class Problem00221 {
    public static void main(String[] args) {
        println(3);
        println(5);
    }

    public static void println(int n) {
        Solution ss = new Solution();
        System.out.println(n + "," + ss.generateParenthesis(n));
    }

    private static class Solution {

        /**
         * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
         * <p>
         * 提示：
         * <p>
         * 1 <= n <= 8
         * <p>
         * 解题思路:
         * 暴力
         *
         * @param n
         * @return
         */
        public List<String> generateParenthesis(int n) {
            List<String> list = new ArrayList<>();
            backtrack(list, new StringBuilder(), 0, 0, n);
            return list;
        }

        public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
            if (cur.length() == 2 * max) {
                ans.add(cur.toString());
                return;
            }

            if (open < max) {
                cur.append('(');
                backtrack(ans, cur, open + 1, close, max);
                cur.deleteCharAt(cur.length() - 1);
            }

            if (close < open) {
                cur.append(')');
                backtrack(ans, cur, open, close + 1, max);
                cur.deleteCharAt(cur.length() - 1);
            }
        }
    }
}
